package com.jxb.first;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

public class IntersectionTwoLinkedLists {

    public static void main(String[] args) {
        ListNode listNode1 = new ListNode();
        listNode1.val = 4;
        ListNode listNode2 = new ListNode();
        listNode2.val = 1;
        ListNode listNode3 = new ListNode();
        listNode3.val = 8;
        ListNode listNode4 = new ListNode();
        listNode4.val = 4;
        ListNode listNode5 = new ListNode();
        listNode5.val = 5;
        listNode4.next = listNode5;
        listNode3.next = listNode4;
        listNode2.next = listNode3;
        listNode1.next = listNode2;

        ListNode listNodeb1 = new ListNode();
        listNodeb1.val = 5;
        ListNode listNodeb2 = new ListNode();
        listNodeb2.val = 6;
        ListNode listNodeb3 = new ListNode();
        listNodeb3.val = 1;
        ListNode listNodeb4 = new ListNode();
        listNodeb4.val = 8;
        ListNode listNodeb5 = new ListNode();
        listNodeb5.val = 4;
        ListNode listNodeb6 = new ListNode();
        listNodeb6.val = 5;
        listNodeb5.next = listNodeb6;
        listNodeb4.next = listNodeb5;
        listNodeb3.next = listNodeb4;
        listNodeb2.next = listNodeb3;
        listNodeb1.next = listNodeb2;

        ListNode listNode = DuPa(listNode1, listNodeb1);
        System.out.println("===="+listNode.val);

    }

    //暴力解法-这种方式相交节点无法确定；时间复杂度O(mn)，空间复杂度为O(1)
    public static ListNode baoLi(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        int L1=0,L2=0;
        ListNode head1 = headA , head2 = headB;
        while(head1 != null){
            L1++;
            head1 = head1.next;
        }
        while(head2 != null){
            L2++;
            head2 = head2.next;
        }
        if (L1 > L2) {
            while (headA != null) {
                while (headB != null) {
                    if (headA == headB) {
                        return headB;
                    }
                    headB = headB.next;
                }
                headA = headA.next;
            }
        }
        return null;
    }

    //hash表-时间复杂度O(m)+O(n),空间复杂度为O(m)+O(n)
    public static ListNode hash(ListNode headA, ListNode headB) {
        ListNode listNode1 = headA;
        ListNode listNode2 = headB;
        Set<ListNode> set = new HashSet<>();
        while (listNode1 != null) {
            set.add(listNode1);
            listNode1 = listNode1.next;
        }

        while (listNode2 != null) {
            if (set.contains(listNode2)) {
                return listNode2;
            }
            listNode2 = listNode2.next;
        }
        return null;
    }
    //双指针-时间复杂度O(n)或者O(m),空间复杂度O(1)
    public static ListNode DuPa(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }
        ListNode pA = headA,pB = headB;
        while (pA != pB) {
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }
        return pA;
    }
    //计算2个链表的长度差，然后从较长的链表开始移动差值，然后再一起移动，直至值相等-复杂度为O(m+n)，空间复杂度为O(1)。
    public static ListNode diff(ListNode headA, ListNode headB) {
        int L1=0,L2=0, diff=0;
        ListNode head1 = headA , head2 = headB;
        while(head1 != null){
            L1++;
            head1 = head1.next;
        }
        while(head2 != null){
            L2++;
            head2 = head2.next;
        }

        if (L1 < L2) {
            diff = L2 - L1;
            head1 = headB;
            head2 = headA;
        }else {
            diff = L1 - L2;
            head2 = headB;
            head1 = headA;
        }

        for (int i = 0;i<diff;i++) {
            head1 = head1.next;
        }
        while (head1 != null && head2 != null) {
            if (head1 == head2) {
                return head1;
            }
            head1 = head1.next;
            head2 = head2.next;
        }
        return null;
    }
}
